package com.huangyi;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 最长递增子序列的个数
    static class Solution {
        public int findNumberOfLIS(int[] nums) {
            int n = nums.length;
            int[] dp = new int[n];
            int[] count = new int[n];
            Arrays.fill(dp, 1);
            Arrays.fill(count, 1);
            int maxLen = 1;

            for (int i = 1; i < n; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        if (dp[j] + 1 > dp[i]) {
                            dp[i] = dp[j] + 1; // 统计的是最大长度
                            count[i] = count[j]; // 用 count[j] 覆盖 count[i] 最大长度的个数
                        } else if (dp[j] + 1 == dp[i]) {
                            count[i] += count[j]; // 继承 count[j] 并更新 count[i] 最大长度的个数
                        }
                    }
                }
                maxLen = Math.max(maxLen, dp[i]);
            }

            int ret = 0;
            for (int i = 0; i < n; i++) {
                if (dp[i] == maxLen) ret += count[i];
            }

            return ret;
        }
    }
}